INTRODUCTION:

Movements of nodes in a mobile ad hoc network cause the nodes to move in and out of range from one another. As the result, there is a continuous making and breaking of links in the network, making the network connectivity (topology) to vary dynamically with time. Since the network relies on multi-hop transmissions for communication, this imposes major challenges for the network layer to determine the multi-hop route over which data packets can be transmitted between a given pair of source and destination nodes. Because of this time-varying nature of the topology of mobile ad hoc networks, traditional routing techniques, such as the shortest-path and link-state protocols that are used in fixed networks, cannot be directly applied to ad hoc networks. A fundamental quality of routing protocols for ad hoc networks is that they must dynamically adapt to variations of the network topology. This is implemented by devising techniques for efficiently tracking changes in the network topology and rediscovering new routes when older ones are broken.

Since an ad hoc network is infrastructure less, these operations are to be performed in a distributed fashion with the collective cooperation of all nodes in the network. Because of its many challenges, routing has been a primary focus of researchers in mobile ad hoc networks.

The MANET working group in the IETF has been working on the issue of standardizing an IP based routing standard for mobile ad hoc networks. Consequently, a large number of dynamic routing protocols applicable to mobile ad hoc networks have been developed. Based on when routing activities are initiated, routing protocols for mobile ad hoc networks may be broadly classified into three basic categories: (a) proactive or table-driven protocols, (b) reactive or on-demand routing protocols, and (c) hybrid routing protocols

Traditional distance-vector and link-state routing protocols¹ are proactive in that they maintain routes to all nodes, including nodes to which no packets are sent. For that reason they require a periodic control message, which leads to scarce resources such as power and link bandwidth being used more frequently for control traffic as mobility increases. One example of a proactive routing protocol is Optimized Link State Routing Protocol (OLSR)². OLSR, which has managed to reduce the utilization of bandwidth significantly. Reactive routing protocols, on the other hand, operate only when there is a need of communication between two nodes. This approach allows the nodes to focus either on routes that are being used or on routes that are in process of being set up. Examples of reactive routing protocols are Ad hoc On- Demand Distance Vector (AODV)³, and Dynamic Source Routing (DSR)⁴. Both proactive and reactive routing has specific advantages and disadvantages that make them suitable for certain types of scenarios. Proactive routing protocols have their routing tables updated at all times, thus the delay before sending a packet is minimal. However, routing tables that are always updated require periodic control messages that are flooded through the whole network- an operation that consumes a lot of time, bandwidth and energy. On the other hand, reactive routing protocols determine routes between nodes only when they are explicitly needed to route packets. However, whenever there is a need for sending a packet, the mobile node must first find the route if the route is not already known. This route discovery process may result inconsiderable delay. Combining the proactive and reactive approaches results in a hybrid routing protocol. A hybrid approach minimizes the disadvantages, but also the advantages of the two combined approaches. The Zone Routing Protocol (ZRP)2⁵ is such a hybrid reactive /proactive routing protocol. Each mobile node proactively maintains routes within a local region (referred to as the routing zone). Mobile nodes residing outside the zone can be reached with reactive routing.

ROUTING PROTOCOLS:

The following three routing protocols are considered in this paper:

A. Destination Sequenced Distance Vector (DSDV):

The DSDV⁶ routing protocol is a proactive routing protocol, described in detail in this paper. It is based on the Bellman-Ford routing algorithm. Each node in the network maintains a routing table which contains all available destinations with associated next hop towards destination, metric and destination sequence number. Sequence number presents improvement of DSDV routing protocol compared to distance vector routing, and it is used to distinguish stale routes from fresh ones and avoid formation of route loops.

Routing tables are updated by exchanging the information between mobile nodes. Each node periodically broadcasts its routing table to its neighbors. Broadcasting of the information is done in Network Protocol Data Units (NPDU) in two ways: a full dump and an incremental dump. A full dump requires multiple NPDUs, while the incremental requires only one NPDU to fit in all the information. A receiving node updates its table if it has received a better or a new route. When an information packet is received from another node, node compares the sequence number with the available sequence number for that entry. If the sequence number is larger, entry will be updated with the routing information with the new sequence number, whereas if the information arrives with the same sequence number, metric entry will be required. If the number of hops is smaller than the previous entry, new information will be updated. Update is performed periodically or when a significant change in the routing table is detected since the last update. If network topology frequently changes, a full dump will be carried out, since an incremental dump will cause less traffic in a stable network topology. Route selection is performed according to the metric and sequence number criteria. The sequence number is also the time indication that destination node sends, allowing routing table update. If we have two identical routes, the route with a larger sequence number will be saved and used, and the other will be destroyed.

B. Ad Hoc On-demand Distance Vector (AODV):

The AODV⁷ routing protocol is an “on demand” routing protocol, which means that routes are established when they are required. This routing protocol is based on transmitting Route Reply (RREP) packets back to the source node and routing data packets to their destination. Used algorithm consists of two steps: route discovery and route maintenance. Route discovery process begins when one of the nodes ants to send packets. That node sends Route Request (RREQ) packets to its neighbors. Neighbors return RREP packets if they have a corresponding route to destination. However, if they don’t have a corresponding route, they forward RREQ packets to their neighbors, except the origin node. Also, hey use these packets to build reverse paths to the source node. This process occurs until a route has been found. Routing tables which only have information about the next hop and destination are used for routing information maintenance. When a route link disconnects, for example, a mobile node is out of range, neighbor nodes will notice the absence of this link. If so, neighbor nodes will check whether there is any route in their routing tables which uses a broken link. If it exists, all sources that send traffic over the broken link will be informed with Route Error (RRER) packet. A source node will generate a new RREQ packet, if there is still a need for packet transmission.

C. Dynamic Source Routing (DSR):

Routing protocol DSR⁸ uses explicit source routing, which means that each time a data packet is sent, it contains the list of nodes it will use to be forwarded. In other words, a sent packet contains the route it will use. Routes are stored in memory, and data packets contain the source route in packet header. Mechanism allows nodes on route to cache new routes, and also, allows source to specify the route that will be used, depending on criteria. This mechanism, also, avoids routing loops. If a node has to send a packet to another one, and it has no route, it initiates a route discovery process. This process is similar to AODV route discovery process. In other words, the network is being flooded with RREQ packets. Each node that receives a RREQ packet, broadcasts it, except for destination node or nodes that have a route to destination node in their memory. A route trough network is built by RREQ packet, and RREP packet is being routed backward to the source. A route that returns RREP packet is cached on the source node for further use. There can be multiple RREP packets on one RREQ packet. In DSR, when a broken link is detected, a RRER packet is sent backward to the source node. After receiving a RRER packet, a source node initiates another route discovery operation. Additionally, all routes containing the broken link should be removed from the route caches. This protocol aggressively uses source routing and route caches.

SIMULATION PARAMETERS:

A. Traffic model:

Traffic model uses Continuous Bit Rate (CBR) traffic sources. This type of traffic is predictable, but unreliable and undirected. Traffic scenarios differ in the number of pairs, which varies in order to change a network load. Those source-destination pairs are spread randomly over the network. In this paper we considered scenarios with 10, 20 and 30 sources. Also, in order to examine the behavior of considered routing protocols, in one set of scenarios we varied the sending rate, while keeping the value of pause time and maximum movement speed fixed. Values of sending rate range from 20 to 200 kbps, pause time is 0 simulation seconds, and maximum movement speed is 20 m/s.

B. Mobility model:

Mobility model uses a random waypoint model in a rectangular field. Node mobility scenario is created for 50 nodes, topology boundary of 500m×500m and simulation time of 100 simulation seconds. Each packet starts traveling from a random location to a random destination with a randomly chosen speed. After a node reaches a destination, it moves to another randomly chosen destination after a pause. Identical movement and traffic scenarios are used across protocols. In one set of scenarios, the duration of pause time, which affects the relative speeds of mobile nodes, is varied, while the value of maximum movement speed and sending rate is kept fixed. Values of pause time are 0, 10, 20, 40 and 100 simulation seconds, movement speed is 20 m/s, and sending rate is 20 kbps. Also, in order to examine the impact of movement speed on performances of routing protocols, we varied the maximum movement speed, while value of pause time and sending rate was kept unchanged. In that case, values of maximum movement speed range from 10 to 50 m/s, while pause time duration is 0 simulation seconds, and sending rate is 100 kbps.

C. Performance metrics⁴,⁹

1) Packet Delivery Ratio (PDR):

PDR shows how successful a protocol is in delivering packets from source to destination. Equation for PDR is:

where n is number of received packets, and m is number of sent packets.

2) Average End to End delay:

This is the average end to end delay of all successfully transmitted data packets from source to destination. Equation for average end to end delay is:

Where, n is number of received packets.

3) Normalized Routing Load (NRL):

NRL is the number of routing packets transmitted per data packet delivered at the destination. Equation for NRL is:

Where, n is number of received packets, and k is number of routing packets

ANALYSIS:

We carried out simulations with 10, 20 and 30 sources, only results with 20 sources are presented in this paper. As in [1], “on-demand” routing protocols, AODV and DSR, achieve high values of PDR, which means they are efficient protocols from the point of delivering packets to their destination (Fig. 1). For AODV and DSR protocols, PDR is independent of mobility and number of sources, while DSDV has approximately the same PDR under low mobility. As shown in Table 1 and Table 2, AODV and DSR protocols deliver over 90% of packets for all considered values of pause time and maximum movement speed. Since DSDV protocol uses a “table driven” approach of maintaining routing information, it isn’t adaptive to the route changes that occur under high mobility as AODV and DSR protocols are. That is why it delivers less data packets, which is also shown in Table 1 and Table 2. Therefore, DSDV protocol is not suitable for MANETs, because it is slow. Results obtained by running simulations with a changeable sending rate confirm the previous conclusion, but also show that all three routing protocols don’t perform well when network load increases. As shown in Table 3, when the network load is the largest routing protocols deliver barely 50% of packets.

Figure 1: Classification and examples of ad hoc routing protocols.

In all considered cases, regardless of mobility, source umber or network load, DSR protocol generates significantly less routing load than AODV and DSDV protocols as Fig. 2 shows. In high network load cases, nodes using considered routing protocols send more packets, thereby sending a larger number of routing packets. On the other hand, in high mobility cases, link failures happen very often. Link failures initiate route discoveries in AODV, since nodes have only one route per destination in their routing table. Thus, the frequency of route discovery in AODV is directly proportional to the number of link failures. That is the reason why a major contribution to AODV’s routing overhead comes from RREQ packets. On the other hand, reaction of DSR to link failures in comparison is mild and causes route discoveries less often. The reason is plenty of cached routes at each node and prolongation of route discovery until all cached routes fail. That is the reason why RREQ packets don’t contribute so much to DSR’s routing overhead. A large contribution in DSR comes from RREP packets. Analyzing average end to end delay, we come to the conclusion that DSR routing protocol outperforms AODV and DSDV protocols (Fig. 3), unlike the results obtained in [1], where AODV protocol has the best performances. As said previously, for any network topology change, nodes that use AODV protocol have to send RREQ packets. In other words, a route discovery process has to be activated, because AODV is a routing protocol that has no available route when needed. Because of inefficient route maintenance, average end to end delay is the largest for AODV. On the other hand, DSDV protocol proactively holds routes to all destinations in its table, regardless of topology changes. However, DSR protocol has the best performances, because it doesn’t depend on periodical activities, and it uses source routing and route caching, but also maintains multiple routes per destination. It excels especially in low mobility scenarios, which means that in cases when network topology is stable, routes are not stale and that results in the best performances under consideration. When a network contains a small number of sources or node’s sending rate is low, AODV and DSDV protocols have a similar average end to end delay as DSR, especially when node mobility is low. In that case, the network is less loaded. However, with source number or sending rate increasing, network load is increasing, and average end to end delay for all three protocols, especially AODV and DSDV, becomes larger which can be see in figure no 4.

Fig.2. Packet Delivery Ratio for: a. Pause time; b. Maximum movement speed; c. Sending rate. Legend: AODV (Ad Hoc On-demand Distance Vector); DSDV (Destination Sequenced Distance Vector); DSR (Dynamic Source Routing).

Fig. 3. Normalized Routing Load for: a. Pause time; b. Maximum movement speed; c. Sending rate. Legend: AODV (Ad Hoc On-demand Distance Vector); DSDV (Destination Sequenced Distance Vector); DSR (Dynamic Source Routing).

Fig. 4. Average End to End Delay for: a. Pause time; b. Maximum movement speed; c. Sending rate. Legend: AODV (Ad Hoc On-demand Distance Vector); DSDV (Destination Sequenced Distance Vector); DSR (Dynamic Source Routing).

CONCLUSION:

Routing protocol DSDV uses proactive “table driven” routing, while AODV and DSR use reactive “on-demand” routing. Protocol DSDV periodically updates its routing tables, even in cases when network topology doesn’t change. AODV protocol has inefficient route maintenance, because it has to initiate a route discovery process every time network topology changes. Both protocols, AODV and DSR, use route discovery process, but with different routing mechanisms. In particular, AODV uses routing tables, one route per destination, and destination sequence numbers as a mechanism for determining freshness of routes and route loops prevention. On the other hand, DSR uses source routing and route caching, and doesn’t depend on any periodic or time-based operations. Generally, we can conclude that in low mobility and low load scenarios, all three protocols react in a similar way, while with mobility or load increasing DSR outperforms AODV and DSDV routing protocols. Poor performances of DSR routing protocol, when mobility or load are increased, are the consequence of aggressive use of caching and lack of any mechanism to expire stale routes or determine the reshness of routes when multiple choices are available. However, there are many other challenges to be faced in routing protocols design. A central challenge is the development of the dynamic routing protocol that can efficiently find routes between two communication nodes. Also, in order to analyze and improve existing or new MANET routing protocols, it is desirable to examine other metrics like power consumption, fault tolerance, number of hops, jitter, etc. in various mobility and traffic models.

REFERENCES:

1. S. Shah, et al., “Performance Evaluation of Ad Hoc Routing Protocols Using NS2 Simulation,” Proceedings of the National Conference on Mobile and Pervasive Computing (CoMPC-2008), Chennai, India, August 2008.

2. K. Gorantala, “Routing Protocols in Mobile Ad Hoc Networks,” Master Thesis, Department of Computing Science, Umeøa University, Sweden, June 2006.

3. Z. Bojković, M. Stojanović, and B. Milovanović, “Current Developments towards the 4G Wireless System,” Proceedings of International Conference TELSIKS, Niš, Serbia, September 2005, pp. 229-232.

4. S. Baraković and J. Baraković, “Comparative Performance Evaluation of Mobile Ad Hoc Routing Protocols,” Proceedings of the 33rd International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO 2010), Opatija, Croatia, May 2010.

5. Network Simulator version 2 (NS-2) webpage. Available at: http://www.isi.edu/nsnam/ns, accessed at May 1st, 2010.

6. C. E. Perkins and P. Begat, “Highly Dynamic Destination- Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” Proceedings of the ACM SIGCOMM‘94 Conference on Communications Architectures, Protocols, and Applications, London, United Kingdom, August 1994, pp. 234-244.

7. C. E. Perkins, E. Belding-Royer, and S. Das, “Ad Hoc On-demand Distance Vector (AODV) Routing,” Experimental RFC 3561, Internet Engineering Task Force (IETF), July 2003.

8. D. Johnson, Y. Hu, and D. Maltz, “The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4,” Experimental RFC 4728, Internet Engineering Task Force (IETF), February 2007.

9. N. Usop, A. Abdullah, and A. Abidin, “Performance Evaluation of AODV, DSDV and DSR Routing Protocol in Grid Environment,”International Journal of Computer Science and Network SecurityIJCSNS, vol. 9, No. 7, pp. 261-268, July 2009.

10. N. Meghanathan, “Multicast Extensions to the ocation Prediction Based Routing Protocol for Mobile Ad hoc Networks,” ISAST Transactions on Computers and

Received on 16.07.2011 Accepted on 20.08.2011

Research J. Engineering and Tech. 2(3): July-Sept. 2011 page 179-184